Batch 3 - Class 250 - Computational Thinking 3 (Sorting)

(zoom)

Pre-Class Exercise

(Part of class)

Attendance Kabir, Mihir, Advay, Vansh, Raghav, Angad, Aarkin, Vivaan, Siddharth, Ayush, Aneesh, Harshiet, Shikhar, Arnav, Kushagra, Anshi, Rohan, Rhea, Rehaan

Class Notes:

Review of Computational Thinking - Key elements

Abstraction: There is a graph, with nodes and edges. Abstraction involves focusing on what is important and ignoring the rest - for example, we have not shown how much each tourist attraction cost for entry.

Generalization: Both problems are similar problems - ask students in what respect. Both problems involved going from one point to all other points and coming back to the original problem.

Algorithm: The method to solve the problem. How did you go about traversing the graph? For this kind of the problem, depth first is an intuitive route - you go down a path as far as you can and you backtrack if its the wrong path and try another one.

Pattern Matching: It seems that we can solve any "route finding" problem by drawing a graph for that - this is pattern matching.

Relate to the above in context of the knight's tour, tour guide and circular numbers discussed earlier and search (directory, guess who, 20 questions) discussed last week.

We also learned that searching through a sorted list is much easier than jumbled lists - how do we get the list sorted in the first place.

Sorting Algorithms

Give kids 8 playing cards/numbers each in small groups, and introduce a notion of "comparison" with face down. Ask them to do successive comparisons to sort

One person from the group will present how they sorted, and how many comparisons did they require

Pick out generalizations and differences in their methods, possible

Selection Sort (select the largest number in the list and do repeatedly)
Bubble Sort (bubble the larger number up and do repeatedly)
Ask kids to figure out the number of comparisons in each

Try out Merge sort - "Divide and conquer"

Count the number of comparisons - are they lesser or more than earlier methods?

Applying Computational Thinking to the problems above

What is the "pattern" in sorting problems? Ask kids to come up with some sorting problems in real life.
What is the generalization? What needs to be available in any sorting problem?

Rank ordering of items
Ability to compare them

Amongst the difference problems that students thought about, what are the abstractions? What details are important and what can be ignored?
Ensure that kids understand that the different sorting algorithms are different methods. Those can take different amounts of time.
When we were doing "Guess who" last time, versus "Merge sort" above, what was common to those two algorithms?

"Divide and conquer" is a common pattern that can apply to many problems. Can we solve a set of smaller problems to arrive at a larger solution?
Other examples? Presidential elections in India?

Race Horses

There are 25 horses, but only one race track where 5 horses can race at a time. What is the minimum number of races required to determine the 3 fastest horses in order. Horses can be raced over and over again, and take the same time to run the track.

Answer: 7. Race 5 groups of 5 horses each (5 races). Now race the winners of each race (6th race) - this gives the fastest horse. The next two fastest horses must be out of (a) the second and third from the initial race of the fastest horse; (b) the first and second from the 6th-race-runner-up's initial race; (c) Third horse from the 6th race. Race these 5 horses in the 7th race.
Younger students can solve with 9 horses and 3 tracks, and trying to find out top 2 horses.
Do you see correspondence with sorting? Discuss. Note that each comparison now has five or three points being compared, not two.

Homework:

Sorting Networks (Self Study)

Introduce the notion of parallel computers - what if we can make a number of comparisons in parallel. Then could we sort even faster? How fast?
Draw a Sorting Network for 8 numbers, and get kids to sort on that network

How long does it take to sort on a sorting network?
Ask kids to draw a sorting network for 16 items

Discuss the time taken on each of the above as number of items to be scaled goes up - 100, 1000, 1000000?

References: